
//654.最大二叉树
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        //使用单调栈来存储可能是父节点的位置
        int n=nums.size();
        vector<TreeNode*> tmp(n);
        stack<TreeNode*> st;  //存放可能是父节点的位置 

        int ret=0;    //ret记录最大值的位置,返回值就是最大值对应的节点
        for(int i=0;i<n;i++)
        {
            if(nums[i]>nums[ret]) ret=i;
            TreeNode* cur=new TreeNode(nums[i]);
            while(!st.empty()&&st.top()->val<nums[i])
            {
                cur->left=st.top();    //数组顶部更小,一定不是nums[i]的父节点,一定在nums[i]的左树上
                st.pop();
            }
            if(!st.empty()) st.top()->right=cur;  //找到比他大的位置,其就是它的父节点
            tmp[i]=cur;
            st.push(cur);
        }
        return tmp[ret];
    }
};